package pers.lls.hds.map;


/**
 * 最小生成树
 *
 * @author lilichai
 */
public class MstGraph {
    private final int MAX_VERTS = 20;
    private MstVertex MstVertexList[];
    private int adjMat[][];
    private int nVerts;
    private MstStackX theStack;

    public MstGraph() {
        MstVertexList = new MstVertex[MAX_VERTS];
        adjMat = new int[MAX_VERTS][MAX_VERTS];
        nVerts = 0;
        for (int j = 0; j < MAX_VERTS; j++) {
            for (int k = 0; k < MAX_VERTS; k++) {
                adjMat[j][k] = 0;
            }
        }
        theStack = new MstStackX();
    }

    public void addMstVertex(char lab) {
        MstVertexList[nVerts++] = new MstVertex(lab);
    }

    public void addEdge(int start, int end) {
        adjMat[start][end] = 1;
        adjMat[end][start] = 1;
    }

    public void displayMstVertex(int v) {
        System.out.print(MstVertexList[v].label);
    }

    public void mst() {
        MstVertexList[0].wasVisited = true;
        theStack.push(0);

        while (!theStack.isEmpty()) {
            int currentMstVertex = theStack.peek();

            int v = getAdjUnvisitedMstVertex(currentMstVertex);
            if (v == -1) {
                theStack.pop();
            } else {
                MstVertexList[v].wasVisited = true;
                theStack.push(v);

                displayMstVertex(currentMstVertex);
                displayMstVertex(v);
                System.out.print(" ");
            }
        }

        for (int j = 0; j < nVerts; j++)
            MstVertexList[j].wasVisited = false;
    }

    public int getAdjUnvisitedMstVertex(int v) {
        for (int j = 0; j < nVerts; j++)
            if (adjMat[v][j] == 1 && MstVertexList[j].wasVisited == false)
                return j;
        return -1;
    }

    public static void main(String[] args) {
        MstGraph theMstGraph = new MstGraph();
        theMstGraph.addMstVertex('A');
        theMstGraph.addMstVertex('B');
        theMstGraph.addMstVertex('C');
        theMstGraph.addMstVertex('D');
        theMstGraph.addMstVertex('E');

        theMstGraph.addEdge(0, 1);
        theMstGraph.addEdge(0, 2);
        theMstGraph.addEdge(0, 3);
        theMstGraph.addEdge(0, 4);
        theMstGraph.addEdge(1, 2);
        theMstGraph.addEdge(1, 3);
        theMstGraph.addEdge(1, 4);
        theMstGraph.addEdge(2, 3);
        theMstGraph.addEdge(2, 4);
        theMstGraph.addEdge(3, 4);

        System.out.print("Minimum spanning tree: ");
        theMstGraph.mst();
        System.out.println();
    }

}

class MstStackX {
    private final int SIZE = 20;
    private int[] st;
    private int top;

    public MstStackX() {
        st = new int[SIZE];
        top = -1;
    }

    public void push(int j) {
        st[++top] = j;
    }

    public int pop() {
        return st[top--];
    }

    public int peek() {
        return st[top];
    }

    public boolean isEmpty() {
        return (top == -1);
    }

}

class MstVertex {
    public char label;
    public boolean wasVisited;

    public MstVertex(char lab) {
        label = lab;
        wasVisited = false;
    }

}
